package zcw.com.lib_leet_code;

/**
 * Created by 朱城委 on 2022/1/27.<br><br>
 *
 * 中等：组合总和 Ⅳ
 */
public class Topic377 {
    public static void main(String[] args) {
        Topic377 instance = new Topic377();

        int[] array = new int[] {1,2,3};
        System.out.println(instance.combinationSum4(array, 4));

        array = new int[] {9};
        System.out.println(instance.combinationSum4(array, 3));

        array = new int[] {4, 2, 1};
        System.out.println(instance.combinationSum4(array, 32));
    }

    public int combinationSum4(int[] nums, int target) {
        int[] array = new int[target + 1];
        array[0] = 1;

        for(int i = 1; i <= target; i++) {
            for(int value : nums) {
                if(value <= i) {
                    array[i] += array[i - value];
                }
            }
        }

        return array[target];
    }
}
